"""
给定初始单词，结束单词，以及单词列表
要求找到最短的路径从初始到结束。相邻单词有且只有一个字母不同
成批扩展要用deque，因为Queue无法拿到长度。
共51个点，第50个超时
后来发现是意外，常规来说，应该在第37个点超时
无论是成批，还是双向
无论是使用dequeu、Queue，还是自定义一次性队列
总之，Python写广搜就是容易超时（以前在牛客也有过）。
同样的原理用C++，轻松通过
"""
from collections import deque
from typing import List


class Solution:
    def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:
        D, G = Solution.init(beginWord, wordList)
        if not endWord in D: return 0

        dst = D[endWord]
        flag = set()
        Q = deque() # 不用Queue，因为没有长度
        Q.append(1)
        flag.add(1)
        ans = 0
        while len(Q) != 0:
            ans += 1
            sz = len(Q)
            for i in range(sz):
                h = Q.popleft()
                for v in G[h]:
                    if v in flag: continue
                    if v == dst: return ans + 1
                    Q.append(v)
                    flag.add(v)
        return 0

    @staticmethod
    def init(beginWord: str, wordList: List[str]) -> tuple[dict, List[List[int]]]:
        d = {beginWord: 1}
        for i, si in enumerate(wordList):
            if si == beginWord: continue
            d[si] = i + 2

        n = len(wordList) + 1
        g = [[] for i in range(n + 1)]
        def isok(s: str, t: str) -> bool:
            c = 0
            for si, ti in zip(s, t):
                if si != ti:
                    c += 1
                    if c > 1: return False
            return c == 1

        for i, si in enumerate(wordList):
            a = i + 2
            if isok(beginWord, si):
                g[1].append(a)
                g[a].append(1)
            for j in range(i + 1, len(wordList)):
                if isok(si, wordList[j]):
                    g[a].append(j + 2)
                    g[j + 2].append(a)
        return (d, g)